package com.goudan.practice.array;

/**
 * 先升序后降序的一个数组，二分查找最大值
 */
public class FindMaxVal {

    private static int[] req = {1, 3, 4, 56, 78, 99, 101, 98, 76, 73, 6, 2};

    public static void main(String[] args) {
//        System.out.println(findMaxVal(req));
        System.out.println(process(req, 0, req.length - 1));
    }

    public static int findMaxVal(int[] req) {
        int left = 0;
        int right = req.length;
        int mid = 0;
        while (left < right) {
            mid = left + (right - left) >> 1;
            if (req[mid] > req[mid - 1] && req[mid] < req[mid + 1]) {
                left = mid;
            }
            if (req[mid + 1] < req[mid] && req[mid] < req[mid - 1]) {
                right = mid;
            }
            if (req[mid] > req[mid - 1] && req[mid] > req[mid + 1]) {
                return mid;
            }
        }
        return mid;
    }

    /**
     * 递归解法
     * arr[L..R]范围上求最大值  L ... R   N
     */

    public static int process(int[] arr, int L, int R) {
        // arr[L..R]范围上只有一个数，直接返回，base case
        if (L == R) {
            return arr[L];
        }
        // L...R 不只一个数
        // mid = (L + R) / 2
        int mid = L + ((R - L) >> 1); // 中点   	1
        int leftMax = process(arr, L, mid);
        int rightMax = process(arr, mid + 1, R);
        return Math.max(leftMax, rightMax);
    }

}
